5.9 KB · ⇊ 2 parts · ⤓ Micron 5.9 KB · ⤓ HTML 22.6 KB

top

Übergangsgraphen sind spezielle gerichtete Graphen mit Kantengewichten, die eine Verbindung zwischen Stochastik und Graphentheorie schlagen. Sie eignen sich besonders zur anschaulichen Darstellung von zeitdiskreten homogenen Markow-Ketten.

• Definition

• Verwendung

• Anwendungsbeispiel

• Literatur

Ein gerichteter und kantengewichteter Graph G {\displaystyle G} heißt Übergangsgraph, wenn für jeden Knoten i {\displaystyle i} die Kantengewichte der von i {\displaystyle i} ausgehenden Kanten größer 0 sind und sich zu 1 aufsummieren:

∑ ∑ j ∈ ∈ N G + ( i ) c i j = 1 {\displaystyle \sum _{j\in N_{G}^{+}(i)}c_{ij}=1} .

Dabei ist N G + ( i ) {\displaystyle N_{G}^{+}(i)} die Nachfolgermenge von Knoten i {\displaystyle i} , also die Menge aller Knoten, die durch von i {\displaystyle i} ausgehende Kanten erreicht werden können.

Äquivalent dazu ist, dass der Graph G {\displaystyle G} Adjazenzgraph einer zeilenstochastischen Matrix ist.

Übergangsgraphen dienen zur anschaulichen Darstellung von homogenen Markow-Ketten mit endlichem Zustandsraum in diskreter Zeit. Dabei entspricht jeder Knoten einem Zustand des Systems und die Kantengewichte sind die Übergangswahrscheinlichkeiten zwischen den Zuständen. Dann ist c i j {\displaystyle c_{ij}} genau die Wahrscheinlichkeit, vom Zustand i {\displaystyle i} in den Zustand j {\displaystyle j} zu wechseln. Einige Eigenschaften der Markow-Kette finden sich direkt im Übergangsgraph wieder:

• Der Übergangsgraph ist genau dann stark zusammenhängend, wenn die Markow-Kette irreduzibel ist.

• Der Zustand j {\displaystyle j} ist von dem Zustand i {\displaystyle i} aus erreichbar, wenn es einen i − − j {\displaystyle i-j} -Pfad im Übergangsgraph gibt.

• Zwei Zustände i und j kommunizieren genau dann, wenn sowohl ein i − − j {\displaystyle i-j} -Pfad als auch ein j − − i {\displaystyle j-i} -Pfad im Übergangsgraph existiert.

• Ist der Übergangsgraph bipartit, so hat jeder Zustand der Markow-Kette gerade Periode.

• Ist der Übergangsgraph bipartit und zusammenhängend, so hat die Markow-Kette gerade Periode.

Mit Hilfe von Übergangsgraphen lässt sich das Wahl- und Kaufverhalten visualisieren. Dargestellt werden die prozentuale Zahl von Wieder- und Wechselwählern. Bezogen auf die obigen Abbildung würden 60 % der Partei bzw. dem Produkt A treu bleiben und 40 % zu Partei bzw. Produkt E wechseln. Die Zahl der Wiederwähler bei Partei bzw. Produkt E liegt bei 30 %, die Zahl der Wechselwähler bei 70 %. Allerdings wird der Übergangsgraph schon ab vier Parteien bzw. Produkten recht unübersichtlich.

• Hans-Otto Georgii: Stochastik. Einführung in die Wahrscheinlichkeitstheorie und Statistik. 4. Auflage. Walter de Gruyter, Berlin 2009, ISBN 978-3-11-021526-7, doi:10.1515/9783110215274.

• Marion Patyna, Klaus Schilling: Lineare Algebra: Mehrstufige Prozesse – Matrizenrechnung, Eins Verlag Köln, 1. Auflage 2011, S. 104–118, ISBN 978-3-427-04440-6.